package com.lw.leetcode.hash.b;

import java.util.*;

/**
 * 945. 使数组唯一的最小增量
 *
 * @Author liw
 * @Date 2021/6/23 15:27
 * @Version 1.0
 */
public class MinIncrementForUnique {

    public static void main(String[] args) {
        MinIncrementForUnique test = new MinIncrementForUnique();

        // [3,2,1,2,1,7]
        int[] arr = {3,2,1,2,1,7};
//        int[] arr = {1,2,2,2};
        int i = test.minIncrementForUnique(arr);
        System.out.println(i);
    }

    public int minIncrementForUnique(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.merge(num, 1, (a, b) -> a + b);
        }
        int size = map.size();
        int[] arr = new int[size];
        int n = 0;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            arr[n++] = entry.getKey();
        }
        Arrays.sort(arr);
        int sum = 0;
        for (int key : arr) {
            int value = map.get(key) - 1;
            if (value > 0) {
                sum += value;
                key++;
                while (value != 0 && map.get(key) == null) {
                    key++;
                    value--;
                    sum += value;
                }
                if (value != 0) {
                    map.put(key ,  map.get(key) + value);
                }
            }
        }
        return sum;
    }

}
